package top.minuy.structure.graph.sort;

import top.minuy.structure.graph.cycle.directed.DirectedCycleDetection;
import top.minuy.structure.graph.representations.table.Graph;
import top.minuy.structure.graph.search.depth.GraphDFS;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 拓扑排序，另一个方法，深度优先遍历的后序遍历
 *
 * @author Minuy
 * @time 14:14
 * @date 2021/11/27
 */
public class TopologicalSortDFS {

    private boolean hasCycle;
    private ArrayList<Integer> res;

    public TopologicalSortDFS(Graph g) {
        if (!g.isDirected()) {
            throw new IllegalArgumentException("TopologicalSort only works in directed graph.");
        }

        res = new ArrayList<>();

        // 检测环
        DirectedCycleDetection dcd = new DirectedCycleDetection(g);
        hasCycle = dcd.hasCycle();
        if (hasCycle) {
            return;
        }

        // 深度优先遍历（后序）
        GraphDFS dfs = new GraphDFS(g);
        for (int v : dfs.post()) {
            res.add(v);
        }

        // 倒序结果
        Collections.reverse(res);
    }

    /**
     * 获取有向图有没有环
     *
     * @return boolean 有没有环
     * @author Minuy
     * @date 2021/11/27 13:53
     */
    public boolean hasCycle() {
        return hasCycle;
    }

    /**
     * 获取拓扑排序的结果
     *
     * @return Iterable<Integer> 拓扑排序的结果
     * @author Minuy
     * @date 2021/11/27 13:53
     */
    public Iterable<Integer> sortResult() {
        return res;
    }
}
